The invention relates to a multiple read method for a static or dynamic set of tags each with an ID code and located in the electromagnetic field transmitted by a polling device. The invention also relates to a system implementing this method.
In general, the invention applies to all transactions between a polling system and answering systems (tags) the number of which is not known beforehand. In particular, the invention is applied in the field of recognizing persons bearing badges, or in the fields of counting and controlling objects bearing tags, such as luggage at an airport, goods in a store, or else products in a production line.
Professionals presently know numerous systems and methods for identifying tagged objects. Most of them apply to reading multiple tags, also called xe2x80x9cmultiple readxe2x80x9d.
The multiple tag read methods presently known can be grouped according to three main sorting categories: space related sorting, frequency dependent sorting and time dependent sorting.
The methods based on space related sorting are for separating the tags by modifying the volume processed by the polling device. This is done by modifying the field radiated by the polling device, using different transmission power levels and/or several transmitters.
The second sorting category is that of separating tags depending on frequency. In this case, each tag transmits, at a given frequency depending either on its code or on a band not occupied by others, or else on any other predefined criterion.
The third sorting category, i.e. time dependent sorting, is the one most frequently used in known methods. It consists in spreading the exchanges between the polling device and the tags in time and thus requires a particular protocol. This is the type of method requiring the least hardware means to be implemented. For this type of read method, two major approaches can be distinguished:
methods called xe2x80x9csynchronousxe2x80x9d, where the interrogator is the master; and
asynchronous methods, in which the tags start transmitting as soon as they enter the electromagnetic field of the polling device.
Some of the known methods provide retransmission of the tag code, after a random delay peculiar to each tag, when a collision of messages being transmitted simultaneously by the tags is detected.
There are also methods that consist in leaving a particular time slice for a tag""s response. Each time slice is determined uniquely by the ID code of each tag. However, these methods do not optimize the transaction time between the polling device and the set of tags. Moreover, the time required by the method for reading all the tags can be based on the drawing of random numbers, in addition to the hazard of the number of tags present, which implies that it is not deterministic.
Among the methods of the time sorting category, there is the method described in the French patent application FR-A-2 677 135. This patent application describes a synchronous binary tree time approach.
More precisely, this patent application describes how the device makes the tags present in the polling field of the polling device supply successively each bit of their ID code until this code has been entirely identified. For this purpose, the tags respond to a control signal from the polling device; when a tag detects that the code currently being identified is different from its own, then it temporarily locks up i.e. it goes silent, so that the identification cycle continues with the other tags until there is only one unlocked tag left. The code of this tag is then identified. At the end of the identification cycle, upon a single command from the interrogator, the identified tag locks up permanently and the other tags end their temporary locking. The identification method is then reinitialized for identifying another tag. These operations are repeated as many times as required until all the tags have been identified one by one.
This method of successively identifying each code is the same as scanning through a binary search tree, each branch of which represents one of the two possible values of an ID code bit.
According to this method, the search tree is scanned completely, from the root, for identifying each code. Therefore, the same branch of the binary search tree can be scanned several times. According to this method, the polling time of the tags is consequently rather lengthy as scanning the binary tree is done from the tree root on for each of the tags. This gives a read time of Nxc3x97n, considering that N is the ID code length and n the number of tags present. This method is therefore all the longer the higher the number of tags.
Furthermore, the method described in this patent application can only be applied to a static set of tags that can only be read once.
It is precisely the, object of the invention to remedy the disadvantages of the previously mentioned methods.
For this purpose, it provides a multiple read method for a set of static or dynamic tags, wherein it is not necessary during the polling procedure to go back to the root of the binary search tree for each ID code, which enables to reduce significantly the time required for identifying these tags. The invention also provides a system for implementing this method.
More precisely, the invention relates to a method for reading a set of tags, each with a distinct binary ID code and located in the electromagnetic field of a polling device, consisting of an identification of the binary tag codes by means of transmitting and receiving signals between the polling device and the tags. This method is characterized by the codes all having the same size N, identification of these codes being done successively, bit by bit, by scanning a binary search tree with       ∑          i      =      1        N    ⁢      xe2x80x83    ⁢      2    1  
branches, each branch representing the value 0 or 1 of the N bits and being connected to the branch of the complementary value 1 or 0 via a node. Each branch of the search tree is read only once during a tag set read sequence.
Thus, the method according to the invention has the advantage that it can run in a period of time T (N,n) less than Nxc3x97n (n being big but n being small before 2N). If all tags possible were present, there would be a maximum of 2Nxe2x88x921 different codes and therefore xcex1xc3x972(2Nxe2x88x921) basic transactions for the first request, with xcex1 being a constant representing the ratio of the basic transaction times and which, according to the invention (and according to patent FR-A-2 672 135), is less than 2.
The polling device stores each node of the search tree and each tag stores the last node scanned during its code identification sequence.
According to an embodiment of the invention, the method consists in scanning the binary search tree, widthwise first.
According to another embodiment of the invention, this method consists in scanning the binary search tree, depthwise first.
The invention also relates to a system for reading a dynamic set of tags through a polling device, the tags and the polling device each comprising signal transmitting/receiving means as well as a storage means, characterized in that the polling device comprises:
a tag counter for counting the number of tags present in the field of the polling device;
a bit position counter;
a storage register for the list of codes read or currently being read; and
a pointer for pointing to this code list, and in that each tag comprises:
a sequence number counter;
a sequence number decounter;
a tag counter;
a bit position counter; and
a first read latch.
Advantageously, the polling device and the tags each comprise a tag decounter.